<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html> <head>
<title>Using type inference to make web templates robust against XSS</title>
<style>
h1 { text-align: center }
code { white-space: nowrap }
.printonly { display: none }
@media print {
  .printonly { display: auto }
  .noprint { display: none }
}
</style>
<script>
var shortVersion = /[?&]short(?!==0)/.test(location.search);
var printableVersion = /[?&]printable(?!==0)/.test(location.search);
if (printableVersion) {
  document.write('<style>body { margin: .75in; font-size: 10pt } h1 { font-size: 175% }<\/style>');
} else {
  document.write('<style>body, td, th { font-size: 150% }<\/style>');
}
</script>
<script>(function () {
  var handlers = [];
  this.registerOnLoad = function (handler) {
    if (handlers === null) {
      setTimeout(handler, 0);
    } else {
      handlers.push(handler);
    }
  };

  this.dispatchOnLoad = function () {
    var toDispatch = handlers;
    handlers = null;
    for (var i = 0, n = toDispatch.length; i !== n; ++i) {
      setTimeout(toDispatch[i], 0);
    }
  };
})();</script>

<link href="//google-code-prettify.googlecode.com/svn/trunk/src/prettify.css" type="text/css" rel="stylesheet" />
<script src="//google-code-prettify.googlecode.com/svn/trunk/src/prettify.js" type="text/javascript"></script>
<script src="//google-code-prettify.googlecode.com/svn/trunk/src/lang-css.js" type="text/javascript"></script>
<script>
registerOnLoad(prettyPrint);
</script>
</head>

<body onload="dispatchOnLoad()">
<small style="float:right" class="noprint">
  [<a id="printable-link"></a>]
  [<a id="full-link"></a>]
<script>registerOnLoad(function () {  // After the references are computed
  var plink = document.getElementById('printable-link');
  var flink = document.getElementById('full-link');
  function text(s) { return document.createTextNode(s); }
  if (printableVersion) {
    plink.href = location.pathname + (shortVersion ? '?short' : '');
    plink.appendChild(text('clickable'));
  } else {
    plink.href = location.pathname + (shortVersion ? '?printable&short' : '?printable');
    plink.appendChild(text('printable'));
 }
  if (shortVersion) {
    flink.href = location.pathname + (printableVersion ? '?printable' : '');
    flink.appendChild(text('long'));
  } else {
    flink.href = location.pathname + (printableVersion ? '?printable&short' : '?short');
    flink.appendChild(text('short'));
  }
});
</script>
</small>
<h1>Using type inference to make web templates robust against XSS</h1>
<p>Mike Samuel &lt;msamuel@google.com&gt;, Prateek Saxena &lt;prateeks@eecs.berkeley.edu&gt;</p>

<h2 class="fullversiononly">Contents</h2>
<ul id="toc" class="fullversiononly">
</ul>
<script>registerOnLoad(function () {
  var headers = [];
  (function findHeaders(node) {
    if (node.nodeType === 1/*Element*/) {
      if (/^H[1-6]$/i.test(node.nodeName)) {
        headers.push(node);
      } else {
        for (var child = node.firstChild; child; child = child.nextSibling) {
          findHeaders(child);
        }
      }
    }
  })(document.body);
  var headerStack = [document.getElementById('toc')];
  for (var i = 0, n = headers.length; i < n; ++i) {
    var header = headers[i];
    if (!header.id) {
      var baseId = (header.innerText || header.textContent || '')
          .replace(/[\W+]/g, '_').replace(/^_|_$/g, '').toLowerCase();
      var suffix = '';
      while (document.getElementById(baseId + suffix)) { ++suffix; }
      header.id = baseId + suffix;
    }
    var headerLevel = +header.nodeName.substring(1);  // 'H2' -> 2
    if (headerLevel >= 4) { continue; }
    while (headerStack.length < headerLevel) {
      var list = document.createElement('UL');
      headerStack[headerStack.length - 1].lastChild.appendChild(list);
      headerStack.push(list);
    }
    headerStack.length = headerLevel;
    var li = document.createElement('LI');
    var a = document.createElement('A');
    a.href = '#' + header.id;
    a.appendChild(document.createTextNode(
        header.innerText || header.textContent));
    li.appendChild(a);
    headerStack[headerLevel - 1].appendChild(li);
  }
});</script>

<h2 class="fullversiononly">Motivation</h2>

<p>
Scripting vulnerabilities plague web applications today.  To
streamline the output generation from application code, numerous web
templating frameworks have recently emerged and are gaining widespread
adoption. However, existing web frameworks fall short in providing
mechanisms to automatically and context-sensitively sanitize untrusted
data.
</p>

<p>
For example, a naive web template might look like
</p>
<pre class="prettyprint">
&lt;div&gt;{$name}&lt;/div&gt;
</pre>
<p>
but this template is vulnerable to Cross-site scripting (XSS)
vulnerabilities.  An attacker who controls the value of
<code>name</code> could pass in
<code class=prettyprint>&lt;script&gt;document.location = 'http://phishing.com/';&lt;/script&gt;</code>
to redirect users to a malicious site, steal the users credentials or
personal data, or initiate a download of malware.
</p>

<p>
The template author might manually encode name:
</p>
<pre class="prettyprint">
&lt;div&gt;{$name<u> |escapeHTML</u>}&lt;/div&gt;
</pre>
<p>
making sure that the user sees exactly the value of <code>name</code>
as per spec, and defeating this particular attack.
A better web templating system might automatically insert the
<code>|escape***</code> directives, relieving the template author
of the burden.
</p>

<p>
This paper argues that correct sanitization is too important, that manual
sanitization is an unreasonable burden to place on template authors (and
especially maintainers), defines goals that any automatic approach
should satisfy, and introduces an automatic approach that is
particularly suitable for bolting onto existing web templating
languages.
</p>

<p>
In particular, we introduce the new notion of
"context" type qualifiers to represent the contexts in which untrusted
data can be embedded. We propose a new type system that refines the
base type system of a web templating language with the context type
qualifier. Based on the new type system, we design and develop a
context-sensitive auto-sanitization (CSAS) engine which runs during
the compilation stage of a web templating framework to add proper
sanitization and runtime checks to ensure the correct sanitization. We
implement our system in Google Closure Templates, a commercially used
open-source templating framework that is used in GMail, Google Docs
and other applications. We evaluate our type system on 1035 real-world
Closure templates. We demonstrate that our approach achieves both
better security and performance than previous approaches.
</p>

<p>
This system is in the progress of being bolted onto
<a href="jqueryTemplatesTestbed.html">JQuery templates</a> but that
work has not yet been evaluated on production code.
</p>

<h2 class="fullversiononly">Glossary</h2>
<dl id="glossary" class="fullversiononly">
  <dt>Context</dt>
  <dd>A parser state in the combined HTML, CSS, and JavaScript grammar
    used to determine the stack of sanitization routines that need to be
    applied to any untrusted data interpolated at that point to preserve
    the security properties outlined here.</dd>
  <dt>Cross-Site Scripting</dt>
  <dd>A <a href="#glossary-quoting_confusion">quoting confusion</a>
    attack whereby untrusted data naively interpolated into HTML, CSS,
    or JavaScript causes code to run with the privileges of an origin
    not owned by the attacker.</dd>
  <dt>CSS</dt>
  <dd>CSS 2 and 3 plus vendor specific extensions such as
    <code>expression:</code> and comment parsing and error recovery
    quirks so that our sanitization function definitions survive a
    worst-case analysis.  This paper assumes a basic familiarity with
    CSS.
  </dd>
  <dt>Escaper</dt>
  <dd>A <a href="#glossary-sanitization_function">sanitization function</a>
    that takes content in an input language (usually
    <code>text/plain</code>) and produces content in an output
    language.  E.g. the function <code>escapeHTML</code> is an escaper
    that takes plain text, <code>'I &lt;3 Ponies'</code>, and
    transforms that to semantically equivalent HTML by turning HTML
    special characters into entities: <code>'I &amp;lt;3
    Ponies'</code>.  <small>(Escapers may, in the process, break
    hearts.)</small>  See also
    <a href="http://www.owasp.org/index.php/XSS_(Cross_Site_Scripting)_Prevention_Cheat_Sheet#Escaping_.28aka_Output_Encoding.29" title="Escaping aka Output Encoding">OWASP's definition</a>.
  </dd>
  <dt>Filter</dt>
  <dd>A <a href="#glossary-sanitization_function">sanitization function</a>
    that takes a string and either returns it, returns an innocuous
    string, or aborts template processing.  E.g. an untrusted value at
    the start of a URL can specify a powerful protocol such as
    <code>javascript:</code>.  A filter can ensure that an untrusted
    value at the beginning of a URL either contains no protocol or
    contains one in a whitelist (<code>http</code>,
    <code>https</code>, or <code>mailto</code>) and if it finds an
    untrusted value that violates this rule, might return an innocuous
    value such as <code>'#'</code> which defangs the URL.
  </dd>
  <dt>HTML</dt>
  <dd>HTML as parsed by browsers.  Typically HTML5 but we need to deal with
    syntactic quirks from mainstream browser lines as old as IE5.
    This paper assumes a basic familiarity with HTML.</dd>
  <dt>JavaScript</dt>
  <dd>EcmaScript 5 but including vendor specific extensions such as conditional
    compilation directives so that our sanitization function definitions survive a
    worst-case analysis.
    This paper assumes a basic familiarity with JavaScript.</dd>
  <dt>Normalizer</dt>
  <dd>A <a href="#glossary-sanitization_function">sanitization function</a>
    that takes content in an input language and
    produces content in that same language but that can be used in
    more contexts.  E.g. the function <code>normalizeURI</code>
    might make sure that quotes are encoded so that a URI path can be
    embedded in an HTML attribute unchanged :
    <code>'mailto:<u>&lt;</u>Mohammed<span style=color:#888>%20</span><u>"</u>The<span style=color:#888>%20</span>Greatest<u>"</u><span style=color:#888>%20</span>Ali<u>&gt;</u><span style=color:#888>%20</span>ali@gmail.com'</code>
    &rarr;
    <code>'mailto:<u>%3c</u>Mohammed<span style=color:#888>%20</span><u>%22</u>The<span style=color:#888>%20</span>Greatest<u>%22</u><span style=color:#888>%20</span>Ali<u>%3e</u><span style=color:#888>%20</span>ali@gmail.com'</code>
    and a function that strips tags from valid HTML allows the tagless
    HTML to be included in an HTML attribute context.
  </dd>
  <dt>Quoting Confusion</dt>
  <dd>A vulnerability (or an exploitation of such) due to a failure to
    encode data in one language (such as <code>text/plain</code>) before
    concatenating it with content in another language such as
    <code>text/html</code> in the case of XSS.  Other examples of quoting
    confusion include SQL Injection, Shell Injection, and HTTP header splitting.
  </dd>
  <dt>RTTI</dt>
  <dd>RunTime Type Information.  Reflective access to the type of a
    value at the time a program is running.
    RTTI APIs include <code>typeof</code> in C++, C#, JavaScript;
    <code>instanceof</code> in Java and JavaScript;
    <code>Object.instanceof_of?()</code> in Ruby, <code>type</code>
    in python, <code>Object.getClass()</code> in Java; and
    <code>Object.GetType()</code> in C#.</dd>
  <dt>Sanitization Function</dt>
  <dd>A function that takes untrusted data and returns a snippet of
    web content.  There are several kinds of sanitization functions :
    <a href="#glossary-escaper">escapers</a>,
    <a href="#glossary-normalizer">normalizers</a>,
    and <a href="#glossary-filter">filters</a>.</dd>
  <dt>Template</dt>
  <dd>A function from (typically untrusted) data to a string that is
    specified as a DSL that clearly separates static trusted snippets
    of content (usually appearing as literal text) from interpolations
    of untrusted data (usually appearing as expressions or variable
    names).  In this paper the term is used synonymously with "Web
    Template" which is a type of template that produces a string of
    content in a web language : HTML, CSS, or JavaScript.</dd>
  <dt>Trusted Path</dt>
  <dd>The ability of an application or piece of code to establish a
    channel to the user that the user can be sure leads to that piece
    of code.  E.g. Browsers use an unspoofable dialog box for HTTP
    auth to gather passwords, Windows uses Ctrl-Alt-Delete for the
    same purpose, and browsers disallow spoofing of the URL bar so
    that informed users can reliably tell if a page is secure and
    using valid certs.
    See also <a href="http://en.wikipedia.org/wiki/Trusted_path" title="Trusted path">wikipedia</a>.
  </dd>
  <dt>XSS</dt>
  <dd>See <a href="#glossary-cross_site_scripting">Cross-Site Scripting</a></dd>
</dl>
<script>registerOnLoad(function () {  // Fill in IDs for glossary items.
  var dts = document.getElementById('glossary').getElementsByTagName('dt');
  for (var i = 0, n = dts.length; i < n; ++i) {
    var dt = dts[i];
    if (dt.id) { continue; }
    var id = 'glossary-' + (dt.innerText || dt.textContent || '')
        .replace(/[\W+]/g, '_').replace(/^_|_$/g, '').toLowerCase();
    if (!document.getElementById(id)) {
      dt.id = id;
    }
  }
});</script>

<h2>Solution Sketch: A static approach with RTTI to avoid over-escaping.</h2>

<p>
The template below specifies a form whose <code>action</code> depends
on two values <code>$name</code> and <code>$tgt</code> which may
come from untrusted sources.  The
<code>{if &hellip;}&hellip;{else}&hellip;<span class=nocode>{/if}</span></code> branches to
define a dynamic URL.
</p>
<style>
.safe-chunk { border:1px solid green }
.unchecked-safe-chunk { border:1px solid transparent }
.data-hole { background: black; color: black }
.data-hole-filled { background: black; color: white }
</style>
<pre class=prettyprint>
<span class="unchecked-safe-chunk">&lt;form action="</span><span class=nocode>{if $tgt}</span><span class="unchecked-safe-chunk">/</span>{$name}<span class="unchecked-safe-chunk">/handle?tgt=</span>{$tgt}<span class=nocode>{else}</span>/{$name}<span class="unchecked-safe-chunk">/default</span><span class=nocode>{/if}</span><span class="unchecked-safe-chunk">"&gt;Hello </span>{$name}&hellip;
</pre>

<p>
First, we parse the template to find trusted static content, dynamic
"data holes" that may be filled by untrusted data, and flow control
constructs: <code>if</code>, <code>for</code>, etc.  The solid black
portions are the data holes, and the green portions are trusted static
content.
</p>

<pre class=prettyprint>
<span class="safe-chunk">&lt;form action="</span><span class=nocode>{if $tgt}</span><span class="safe-chunk">/</span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span><span class="safe-chunk">/handle?tgt=</span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span><span class=nocode>{else}</span><span class="safe-chunk">/</span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span><span class="safe-chunk">/default</span><span class=nocode>{/if}</span><span class="safe-chunk">"&gt;Hello </span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span>&hellip;
</pre>

<p>Next we do a flow-sensitive analysis, propagating types to determine the context in which each data hole appears.</p>
<pre class=prettyprint style="margin-bottom: 0; padding-bottom: 0">
<span class="safe-chunk">&lt;form action="</span><span class=nocode>{if $tgt}</span><span class="safe-chunk">/</span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span><span class="safe-chunk">/handle?tgt=</span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span><span class=nocode>{else}</span><span class="safe-chunk">/</span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span><span class="safe-chunk">/default</span><span class=nocode>{/if}</span><span class="safe-chunk">"&gt;Hello </span><span class="data-hole nocode">&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;&#x2588;</span>&hellip;
</pre>
<table cellpadding=0 cellspacing=0 summary="inferred contexts">
  <tr>
    <td><small>&uarr;PCDATA</small></td>
    <td><small>&uarr;URL start</small></td>
    <td><small>&uarr;URL path</small></td>
    <td><small>&uarr;URL query</small></td>
    <td><small>&uarr;URL path</small></td>
    <td><small>&uarr;PCDATA</small></td>
  </tr>
  <tr style="font-family: monospace; white-space: pre">
    <td>&nbsp;            &nbsp;</td>
    <td>&nbsp;        &nbsp;</td>
    <td>&nbsp;                 &nbsp;</td>
    <td>&nbsp;           &nbsp;</td>
    <td>&nbsp;                           &nbsp;</td>
  </tr>
</table>

<p style=margin-top:0>
Based on those contexts, we determine the type of content that is expected for each hole.
</p>

<pre class=prettyprint>
<span class="safe-chunk">&lt;form action=&quot;</span><span class=nocode>{if $tgt}</span><span class="safe-chunk">/</span><span class="data-hole-filled nocode">  URL  </span><span class="safe-chunk">/handle?tgt=</span><span class="data-hole-filled nocode">Query </span><span class=nocode>{else}</span><span class="safe-chunk">/</span><span class="data-hole-filled nocode">  URL  </span><span class="safe-chunk">/default</span><span class=nocode>{/if}</span><span class="safe-chunk">&quot;&gt;Hello </span><span class="data-hole-filled nocode"> HTML  </span>&hellip;
</pre>

<p>
Finally we insert calls to <a href="#glossary-sanitization_function">sanitizer functions</a> into the template.
</p>
<pre class=prettyprint>
&lt;form action=&quot;<span class=nocode>{if $tgt}</span>
  /{<ins>escapeHTML</ins>($name)}/handle?tgt={<ins>encodeURIComponent</ins>($tgt)}
<span class=nocode>{else}</span>
  /{<ins>escapeHTML</ins>($name)}/default
<span class=nocode>{/if}</span>
&quot;&gt;Hello {<ins>escapeHTML</ins>($name)}&hellip;
</pre>

<p>
That is the gist of the solution, though the above example glosses
over issues with re-entrant templates, templates that are invoked in
multiple start contexts, and joining branches that end in different
contexts; and the exact sanitization functions chosen are different
than shown in this simplified example.
</p>

<p>
The example only shows HTML and URL encoding, but our solution deals
with data holes that occur inside embedded JavaScript and CSS as any
solution for AJAX applications must.
</p>

<h2>Problem Definition</h2>
<p>
In this section we present several metrics on which any competing
sanitization scheme should be judged, and a definition of a safe
template that can be used to prove or disprove the soundness of a
sanitization scheme that we think is relevant to security properties
that web applications commonly want to enforce.
</p>

<h3>Performance</h3>
<p>
A sanitization scheme should be judged on several performance metrics:
</p>
<ol>
  <li>Compile- or load-time overhead.  The cost of any static analysis.
  <li>Run-time analysis overhead.  The cost of any dynamic analysis
      done when the template is run.
  <li>Run-time sanitization overhead.  The cost of
      <a href="#glossary-sanitization_function">sanitizing</a>
      untrusted data.
  <li>One-time development overhead.  The burden placed on a developer
      to learn the system.
  <li>Continual development overhead.  The burden placed on a developer
      to add sanitization directives, review code to ensure they are
      used correctly, debug the resulting template code, and deal with
      any over- or mis-sanitization.
</ol>

<p>
Run-time analysis overhead (proportional to overall template runtime)
often differs substantially by platform.  High quality
parser-generators exist for C and Java, so the overhead may be much
lower there than in browser, since iterating char by char over a
string is slow in JavaScript.
</p>

<p>
Our proposal has a modest compile-/load-time cost taking slightly less
than 1 second to do static inference for 1035 templates comprising
782kB of source code or about 1ms per template.
The runtime analysis for our proposal is zero.
The runtime sanitization overhead on a benchmark is between 3% and 10%
of the total template execution time, and is indistinguishable from
the overhead when non-contextual auto-sanitization is used (all data holes
sanitized using HTML entity escaping).
</p>

<p>
Development overhead is hard to measure but the 1035 templates were
migrated by an application group in a matter of weeks without stopping
application development with little coordination, so the one-time
overhead &mdash; the overhead to learn the system &mdash; is lower
than that to learn and adopt a new templating language.  Since the
system works by inserting function calls, we provided debugging tools
that diffed templates before and after the inference was run to show
developers what the system was doing and aid in debugging.
Due to the need to debug templates written using any approach, the
continual development overhead can never be zero, but tool support,
like diffing can make the system transparent and ease debugging.
</p>

<p>
Finally, once a bug has been identified, we try to make sure there
are simple bugfixing recipes.
</p>
<ul>
  <li>If the problem is over-escaping of known-safe data values that were
      already sanitized, then wrap the data value in a
      <code>SanitizedContent</code> wrapper object of the appropriate
      type as close to where it is sanitized as possible.  Ideally, an
      HTML tag whitelisting sanitizer would return a value of type
      <code>SanitizedContent</code>.</li>
  <li>If the sanitizer is choosing the wrong sanitization functions for
      whatever reason, insert your own.  The system recognizes
      sanitization functions and does not interfere with developer
      choices.</li>
</ul>

<h3>Ease of Adoption/Migration</h3>
<p>
What kind of changes, if any, do developers have to make to take an
existing codebase of templates and have them properly sanitized?  For
example, adding sanitization functions manually is time-consuming and
error-prone.  Making sure that all static content is valid XHTML
requires repetitive, time-consuming changes, but would not be as
error-prone.
</p>

<p>
Our proposal allows contextual auto-sanitization to be turned on for some
templates and not for others; most templating languages allow
templates to be composed, i.e. templates can call other templates, and
standard practice seems to be to have a few large templates that call
out to many smaller templates.  Since this can be done per template, a
codebase can be migrated piecemeal, starting with complicated
templates that have known problems.
</p>

<p>
Our proposal does not impose an element structure on template
boundaries.
Many top level templates look like:
</p>
<pre class="prettyprint lang-html" id=header-footer-example>
{include "common-header.foo"}
&lt;!-- Body content --&gt;
{include "common-footer.foo"}
</pre>
<p>
where the common header opens elements that are closed in the
common footer:
</p>
<pre class="prettyprint">
&lt;html&gt;&lt;head&gt;
&lt;!-- Common style and script definitions --&gt;
...
&lt;/head&gt;&lt;body&gt;
&lt;!-- Common menus --&gt;
</pre>
<p>
Approaches that require template code to be well-formed XML, such as
XSLT, cannot support this idiom.  Our proposal works for templating
languages that allow this idiom because we propagate types as they flow
template calls rather than inferring types of content based on a DOM
derived from a template.
</p>

<h3>Ease of Abandonment</h3>
<p>
If a development team adopts a sanitization scheme, and finds that it
does not meet their needs, how easily can they switch it off, and how
much of the effort they invested in deploying it can they recover?
</p>

<p>
Since our solution works by inserting calls to sanitization function
into templates, a development team having second thoughts can simply
run the type inference engine to insert the calls, and print out the
resulting templates to generate a patch to their codebase
and then remove whatever directives turned on auto-sanitization.
We argued above that cost of adoption is low, and most of the work
put into verifying that the sanitization functions chosen were
reasonable is recoverable.
</p>

<h3>Security under Maintenance</h3>
<p>
Security measures tend to be removed from code under maintenance.
Imagine a template that is not auto-sanitized:
</p>
<pre class="prettyprint">&lt;div&gt;Your friend, {escapeHTML($name)}, thinks you'll like this.&lt;/div&gt;</pre>
<p>
that is passed a plain text name.  While merging two applications,
developers add a call to this code, passing in a rich HTML signature
that has been proven safe by a tag whitelister, e.g.
<code>"Alan &lt;font color=green&gt;Green&lt;/font&gt;span"</code>.
Eventually, Mr. Greenspan notices that his name is misrendered and
files a bug.  A developer might check that the rich text signature is
sanitized properly before being passed in, but not notice the other
caller that doesn't do any sanitization.  They resolve the bug by
removing the call to <code>escapeHTML</code> which fixes the bug but
opens a vulnerability.
</p>

<p>
Over-encoding is more likely to be noticed by end-users than XSS
vulnerabilities, so a project under maintenance is more likely
to lose manual sanitization directives than to gain them.
</p>

<p>
Our proposal addresses this by introducing
<a href="#sanitized_content_types">sanitized content types</a>
as a principled solution to over-encoding problems.
</p>

<h3>Structure Preservation Property</h3>
<p>
We define a safe template as one that has several properties: the
structure preservation property described here, and the code effect
and least surprise properties defined in later sections.
</p>

<p>
Intuitively, this property holds that when a template author writes
an HTML tag in a safe templating language, the browser will interpret the
corresponding portion of the output as a tag regardless of the values of
untrusted data, and similarly for other structures such as attribute
boundaries and JS and CSS string boundaries.
</p>

<p>
This property can be violated in a number of ways.  E.g. in the
following JavaScript, the author is composing a string that they
expect will contain a single top-level bold element surrounded by
text.
</p>
<pre class=prettyprint>
document.write(greeting + ', &lt;b&gt;' + planet + '&lt;/b&gt;!');
</pre>
<p>
and if <code>greeting</code> is <code>"Hello"</code> and
<code>planet</code> is <code>"World"</code> then this holds as the
output written is
"<code class=prettyprint>Hello,&nbsp;&lt;b&gt;world&lt;/b&gt;!</code>";
but if <code>greeting</code> is
<code>"&lt;script&gt;alert('pwned');//"</code> and <code>planet</code>
is <code>"&lt;/script&gt;"</code> then this does not hold since the
structure has changed: the <code>&lt;b&gt;</code> should have started
a bold element but the browser interprets it as part of a JavaScript
comment in
"<code class=prettyprint>&lt;script&gt;alert('pwned');//,&nbsp;&lt;b&gt;&lt;/script&gt;&lt;/b&gt;!</code>".
</p>

<p>
Lower level encoding attacks, such as
<a href="http://ha.ckers.org/xss.html#XSS_UTF-7" title="ha.ckers.org UTF-7">UTF-7</a>
attacks, may also violate this property.
</p>

<p>
More formally, given any template, e.g.
</p>
<pre class="prettyprint">
&lt;div id="{$id}" onclick="alert('{$message}')"&gt;{$message}&lt;/div&gt;
</pre>
<p>
we can derive an <i>innocuous template</i> by replacing every
untrusted variable with an innocuous string, a string that is not
empty, is not a keyword in any programming language and does not
contain special characters in any of the languages we're dealing with.
We choose our innocuous string so that it is not a substring of the
concatenation of literal string parts.  Using the innocuous string
<code>"zzz"</code>, an innocuous template derived from the above is:
</p>
<pre class="prettyprint">
&lt;div id="zzz" onclick="alert('zzz')"&gt;zzz&lt;/div&gt;
</pre>

<p>
Parsing this, we can derive a tree structure where each inner node
has a type and children, and each leaf has a type and a string value.
</p>
<pre style="line-height:100%">
Element
&nbsp;&#x2560;Name : "div"
&nbsp;&#x2560;Attribute
&nbsp;&#x2551; &#x2560;Name : "id"
&nbsp;&#x2551; &#x255a;Text : "zzz"
&nbsp;&#x2560;Attribute
&nbsp;&#x2551; &#x2560;Name : "onclick"
&nbsp;&#x2551; &#x255a;JsProgram
&nbsp;&#x2551; &nbsp; &#x255a;FunctionCall
&nbsp;&#x2551; &nbsp; &nbsp; &#x2560;Identifier : "alert"
&nbsp;&#x2551; &nbsp; &nbsp; &#x255a;String : "zzz"
&nbsp;&#x255a;Text : "zzz"
</pre>

<p>
A template has the structure preservation property when for all possible
branch decisions through a template, and for all possible data table inputs,
a template either produces no output (fails with an exception) or produces
an output that can be parsed to a tree that is structurally the same as
that produced by the innocuous template derived from it for the same set of
branch decisions.
</p>

<p>
&#x2200; branch-decisions &#x2200; data, areEquivalent(<br>
&nbsp; &nbsp; parse(innocuousTemplate(T)(branch-decisions, data))<br>
&nbsp; &nbsp; parse(T(branch-decisions, data)))
</p>

<p>
where parse parses using a combined HTML/JavaScript/CSS grammar to the
tree structure described above, branch-decisions is a path through
flow control constructs (the conditions in <code>for</code> loops and
<code>if</code> conditions) and where areEquivalent is defined thus:
</p>

<pre class=prettyprint>
def areEquivalent(innocuous_tree, actual_tree):
  if innocuous_tree.is_leaf:
    # innocuous_string was 'zzz' in the example above.
    if innocuous_string in innocuous_tree.leaf_value:
      # Ignore the contents of actual since it was generated by
      # a hole.  We only care that it does not interfere with
      # the structure in which it was embedded.
      return True
    # Leaves structurally the same.
    # Assumes same node type implies actual is leafy.
    return (innocuous_tree.node_type is actual_tree.node_type
            and innocuous_tree.leaf_value == actual_tree.leaf_value)
  # Require type equivalence for inner nodes.
  if node_type(innocuous_tree) is not node_type(actual_tree):
    return False
  # Zip below will silently drop extras.
  if len(innocuous_tree.children) != len(actual_tree.children):
    return False
  # Recurse to children.
  for innocuous_child, actual_child in zip(
      innocuous_tree.children, actual_tree.children):
    if not areEquivalent(innocuous_child, actual_child):
      return False
  return True  # All grounds on which they could be inequivalent disproven.
</pre>

<p>
This definition is not computationally tractable, but can be used as a
basis for correctness proofs, and in practice branch decisions that go
through loops more than twice or recurse more than twice can be
ignored so by using fuzzers to generate bad data inputs, we can gain
confidence in an implementation.
</p>

<p>
This property is essential to capturing developer intent.  When the
developer writes a tag, the browser should interpret that as a tag,
and when the developer writes paired start and end tags, the browser
should interpret those as a matched pair.
It is also important to applications that want to embed sanitized data
while preserving a <a href="#glossary-trusted_path">trusted path</a>
since the structure preservation property is a prerequisite for visual
containment.
</p>


<h3 id="code_effect_property">Code Effect Property</h3>
<p>
Web clients may specify data values in code (strings,
booleans, numbers, JSON) but <i>only</i> code specified by the
template author should run as a result of injecting the template
output into a page and <i>all</i> code specified by the template
author should run as a result of the same.
There are a dizzyingly large number of ways this property can
fail to hold for a template.  A non-exhaustive sample of ways to
cause extra code to run:
</p>
<ul>
  <li>Unencoded text could contain a <code>&lt;script&gt;</code> element.
  <li>A dynamic attribute name could specify an event handler: <code>onclick</code>.
  <li>A dynamic <code>src</code> or <code>href</code> could specify
      <code>javascript</code>, <code>livescript</code>, etc. as the protocol
      in <a href="http://ha.ckers.org/xss.html" title="XSS Cheat Sheet">myriad</a> ways.
  <li><a href="http://code.google.com/p/browsersec/wiki/Part1#Cascading_stylesheets">Dynamic CSS</a>
      could use a vendor-specific extension, e.g.
      <code>expression</code> or <code>-moz-binding</code>.
  <li>A dynamic <code>&lt;object&gt;</code> might load flash cross origin
      and <code>AllowScriptAccess</code>.
  <li>Dynamic values might reach <code>eval</code>, <code>setTimeout</code>, etc.
</ul>

<p>
There are also many ways to cause security-critical code to not run.
In general, it is not wise to rely on JavaScript running in a browser,
but many developers, not unreasonably, rely on some code having run if
other code is running at a later time.
A non-exhaustive sample of ways to stop code running via XSS:
</p>
<ul>
  <li>Change the base href of the page by inserting a
      <code>&lt;base&gt;</code> element disabling <code>src=</code>'ed
      <code>&lt;script&gt;</code>s with relative URLs.
  <li>Inject improperly encoded data into a data hole in an inline
      <code>&lt;script&gt;</code> element that causes it to fail to parse, e.g.
      codepoints U+2028 or U+2029 in a string body.
      <small>(A violation of the Structure Preservation Property).</small>
  <li>Cause an inline event handler or <code>&lt;script&gt;</code> tag
      to not be interpreted as such.
      <small>(A violation of the Structure Preservation Property).</small>
  <li>Insert code that disables, removes, or changes critical APIs:
      <code class=prettyprint>Object.prototype.toString = function() {throw new Error}</code>
  <li>Inject a <code>&lt;noscript&gt;</code> element around the <code>&lt;head&gt;</code>.
      <small>(A violation of the Structure Preservation Property).</small>
  <li>Fool heuristic XSS defense browser plugins into thinking that the
      security code was injected by manipulating query parameters.
</ul>

<p>
Our proposal enforces this property by
<a href="#glossary-filter">filtering</a> URLs to prevent any data
hole from specifying an exotic protocol, by filtering CSS keywords,
and by only allowing data holes in JavaScript contexts to specify
simple boolean, numeric, and string values, or complex JSON values
which cannot have free variables.
We assume that the JavaScript interpreter will work on arbitrarily
large inputs.
<a href="http://www.cse.usf.edu/~ligatti/papers/code-inj.pdf"
>"Defining Code-Injection Attacks"</a> by Ray &amp;
Ligatti defines a similar property: a CIAO (code injection attack on
outputs) occurs when an interpolation causes the parse tree to include
an expression that is not in its normal form, one consequence of which
is that has no free variables.
</p>

</p>

<p>
Finally, our <a href="#glossary-escaper">escapers</a> are designed
to produce output that avoids grammatical such as semicolon insertion,
non-ASCII newline characters,
regular-expression/division-operator/line-comment confusion.
</p>

<p>
Identifying all places in which a URL might appear in HTML
(incl. MathML and SVG) is relatively easy compared to CSS.
In CSS, it is difficult.  For example, in
<code class="prettyprint">&lt;div style="background: {$bg}"&gt;</code>,
<code>$bg</code> might specify a URL, a color name,
a color value like <code>#000</code>, a function-like color
<code>rgb(0,0,0)</code>, a keyword value like
<code>transparent</code>, or a combination of the above.  Given how
hard it is to reliably black-list URLs, when you know the content is a
URL, we took the rather drastic approach of forbidding anything that
might specify a colon in CSS data holes.
<!-- TODO: check that we do this -->
This seems to affect very little in practice, and we could relax this
constraint to allow colons preceded by a safe word like the name of an
element, pseudo-element, or innocuous property.  Even if we did, it is
possible that existing code uses colons in data holes to specify list
separators a la semantic HTML, and we would break that use case:
</p>
<pre class="prettyprint lang-css">
ul.inline li { list-style: none; display: inline }
ul.inline li:before { content: ': ' }  /* ', ' here would give a normal looking list. */
ul.inline li:first-child:before { content: '' }
</pre>

<p>
This property is a prerequisite for many application <i>privacy</i> goals.
If a third-party can cause script to run with the privileges of the origin,
it can steal user data and phone home.  Even if credentials are unavailable
to JavaScript (<a href="http://www.codinghorror.com/blog/2008/08/protecting-your-cookies-httponly.html">HTTPOnly</a> cookies),
scripts with same-origin privileges can screen scrape (using DOM APIs)
user names and identifiers and associated page content and phone home.
</p>

<p>
This property is also a prerequisite for many <i>informed consent</i> goals.
If a third-party script can install <code>onsubmit</code> handlers, it can
rewrite form data before it is submitted with the XSRF tokens that are
meant to ensure that the data submitted was specified by the user.
</p>


<h3>Least Surprise Property</h3>
<p>
The last of the security properties that any auto-sanitization scheme should
preserve is the property of least surprise.  The authors do not know
how to formalize this property.
</p>

<p>
Developer intuition is important.
A developer (or code reviewer) familiar with HTML, CSS, and
JavaScript; who knows that auto-sanitization is happening should be
able to look at a template and correctly infer what happens to dynamic
values without having to read a complex specification document.
Simple rules-of-thumb should be sufficient to understand the system.
E.g. if a mythical average developer sees
<code class=prettyprint>&lt;script&gt;var msg = '{$msg}';&lt;/script&gt;</code>
and their intuition is that <code>$world</code> <i>should</i> be
escaped using JavaScript style <code>\</code> sequences, and that is sufficient to preserve the other
security properties, then that is what the system should do.
Templates should be both easy to write and to code review.
</p>

<p>
Exceptions to the system should be easily audited.
SQL prepared statements are great, but there's no way to have
exceptions to the rule without giving up the whole safety net, so
sometimes developers work around them by concatenating strings.
It's hard to <code>grep</code> (or craft presubmit triggers) for all
the places where concatenated strings are passed to SQL APIs, so it's
hard for a more senior developer to find these after the fact and
explain how naive developers can achieve their goal working within the system,
notice a trend that points to a systemic problem with schemas, or
agree that the exception to the rule is warranted and document it for
future security auditors.
</p>

<p>
Our proposal was designed with this goal in mind, but we have not
managed to quantify our success.  We can note that 1035 templates were
converted within a matter of weeks without a flood of questions to the
mailing lists we monitor, so we infer that most of the parts of the
system that were heavily exercised were non-controversial.
Different communities of developers may have different expectations.
We worked with a group of developers most of whom knew Java, C++, or
both before starting web application development, and among whom a
high proportion have at least a bachelor's degrees in CS or a
related field.
They may differ, intuition-wise, from developers who came to web
development from a Ruby, Perl, or PHP background.
</p>


<h2>Alternate Approaches</h2>
<p>
In this section we introduce a number of alternative proposals,
explain why they perform worse on the metrics above.
We cite real systems as examples of some of these alternatives.
Many of these systems are well-thought out, reasonable solutions to
particular problems their authors faced.
We merely argue that they do not extend well to the criteria we outlined
above and explicitly label these sections "strawmen" to clarify the
difference between our design criteria and the contexts in which these
systems arose.
We do claim though that any comprehensive solution to XSS, at a tools
level, should meet the criteria above.
</p>

<h3>Strawman 0: Manual sanitization</h3>
<p>
Manual sanitization is the state-of-the-art currently.  Developers use
a suite of functions, such as OWASP's open source
<a href="http://code.google.com/p/owasp-esapi-java/source/browse/trunk/src/main/java/org/owasp/esapi/Encoder.java">OSAPI encoders</a>
and every developer must learn when and how to apply them correctly.
They must apply sanitizers either before data reaches a template or
within the template by inserting function calls into code.
</p>

<p>
This places a significant burden on developers and does not guarantee
any of the security properties listed above.  One lapse can undo all
the work put into hardening a website because of the all-or-nothing
nature of the same-origin policy.
</p>

<p>
There is a tradeoff between correctness and simplicity of API that
works in the attackers favor.  Manual sanitization is particularly
error-prone because developers learn <i>the good parts</i> of the
languages they work in, but attackers have available to them <i>the
bad parts</i> as well.  The syntax of HTML, CSS, and JavaScript are
much gnarlier than most developers imagine, and it is an unreasonable
burden to expect them to learn and remember obscure syntactic corner
cases.  These corner cases mean that the typical suite of 4-6 escaping
functions is the most that many developers can reliably choose from,
but they are insufficient to handle corner cases or nested contexts.
</p>

<p>
Changes in language syntax or vendor-specific extensions
(e.g. XML4J and embedded SVG) may invalidate developers previously
valid assumptions.  Code that was safe before may no longer be safe.
With an automated system, a security patch and recompile may suffice,
but a patch to code that took a team of developers years to write will
take a team of developers to fix.
</p>

<p>
XSS Scanners (e.g. <a href="http://googleonlinesecurity.blogspot.com/2007/07/automating-web-application-security.html">lemon</a>)
can mitigate some of manual sanitization's cons (though they work with
any of the other solutions here as well to provide defense-in-depth),
but there are no good scanners for AJAX applications, and, with manual
sanitization, scanners impose a continual burden on developers to respond
to the reported errors.
</p>

<h3>Strawman I: Non-contextual auto-sanitization</h3>

<p>
Non-contextual auto-sanitization is a great improvement over
manual sanitization.
<a href="http://code.djangoproject.com/wiki/AutoEscaping" title="Django autoescaping">Django templates</a> and others use it.
</p>

<p>
It works by assuming that every data hole should be sanitized the same way,
usually by HTML entity encoding.  As such, it is prone to over-escaping and
mis-escaping.
To understand mis-escaping, consider what happens when the
following template is called with <code>', alert('XSS'), '</code> :
</p>
<pre class="prettyprint">
&lt;button onclick="setName('{$name}')"&gt;
</pre>
<p>
The template produces
<code class=prettyprint>&lt;button onclick="setName('&amp;apos;, alert(&amp;apos;XSS &amp;apos;), &amp;apos;')"&gt;</code>
which is exactly the same, to the browser, as
<code class=prettyprint>&lt;button onclick="setName('', alert('XSS '), '')"&gt;</code> because the browser HTML entity
decodes the attribute value <i>before</i> invoking the JavaScript parser on it.
</p>

<p>
Non-contextual auto-sanitization cannot preserve the structure
preservation property for JavaScript, CSS, or URLs because it is
unaware of those languages.
It also fails to preserve the code effect property.
</p>

<p>
Bolting filters on non-contextual auto-sanitization will not help
it to preserve the code effect property.  It is possible to write
bizarre JavaScript that
<a href="http://securitymusings.com/article/2022/code-with-javascript-letters-and-numbers-optional" title="Code with JS letters &amp; numbers&hellip;">does not even need alphanumerics</a>.
Since JavaScript has no regular lexical grammar, regular expressions
that are less than draconian are insufficient to filter out attacks.
</p>

<p>
Non-contextual auto-sanitization, with auditable exceptions like Django's,
does preserve the least surprise property in a sense.  With very little
training, a developer can predict exactly what it will do, and
empirically, 74% of the time it does what they want
(our system chose some kind of HTML entity encoding for 992 out of
1348 data holes).
</p>


<h3>Strawman II: Strict structural containment</h3>
<p>
Examples of strict structural containment languages are
<a href="http://www.w3.org/TR/xslt">XSLT</a>,
<a href="http://code.google.com/p/gxp/">GXP</a>,
<a href="http://www.yesodweb.com/">Yesod</a>, and possibly
<a href="http://www.facebook.com/notes/facebook-engineering/xhp-a-new-way-to-write-php/294003943919">XHP</a>.
For all of these, the input is (or is coercible via
fancy tricks) to a tree structure like XML.  So for every data hole,
it is obvious to the system which element and attribute context the
hole appears in&dagger;.  A similar structural constraint could be
applied in principle to embedded JS, CSS, and URIs.
</p>

<p>
Strict structural containment is a sound, principled approach to
building safe templates that is a great approach for anyone planning a
new template language, but it cannot be bolted onto existing languages though because it requires
that every element and attribute start and end in the same template.
This assumption is violated by several very common idioms, such as the
<a href="#header-footer-example">header-footer idiom</a><span class=printonly>, above,</span>
in ways that often require drastic changes to repair.
</p>

<p>
Since it cannot be bolted onto existing languages, limiting
ourselves to it would doom to insecurity most of the template code
existing today.  Most project managers who know their teams have
trouble writing XSS-free code, know this because they have existing
code written in a language that does not have this property.
</p>

<p><small>
&dagger; - modulo mechanisms like
<a href="http://www.w3.org/TR/xslt#section-Creating-Elements-with-xsl:element" title="Creating Elements with xsl:element"><code>&lt;xsl:element name="..."&gt;</code></a>
which can, in principle, be repaired using equivalence classes of
elements and attributes.  I.e. one could define an equivalence class
of elements all of whose attributes have the same meaning and which
have the same content type: (TBODY, THEAD, TFOOT), (OL, UL), (TD, TH),
(SPAN, I, B, U), (H1, H2, H3, &hellip;) and allow a dynamic element
mechanism to switch between element types within the same equivalence
class.  Similar approaches can allow selecting among equivalent
dynamic attribute types : all event handlers are equivalent (modulo
perhaps those that imply user interaction for some applications).
</small></p>

<h3>Strawman III: A runtime typing approach</h3>
<p>
Prior to this work, the best auto-sanitization scheme was a
<a href="http://googleonlinesecurity.blogspot.com/2009_03_01_archive.html" title="Reducing XSS by way of Automatic Context-Aware Escaping&hellip;">runtime scheme</a>.
</p>

<p>
A runtime contextual auto-sanitizer plugs into a template runtime at a
low level.  Instead of writing content to an output buffer, the
template runtime passes trusted and untrusted chunks to the
auto-sanitizer.  The template:
</p>
<pre class=prettyprint>
&lt;ul&gt;{for $item in $items}&lt;li onclick="alert('{$item}')"&gt;{$item}{/for}&lt;/ul&gt;
</pre>
<p>
might produce the output on the left, and by propagating context at
runtime, infer the context in the middle and choose to apply the
escaping directives on the right before writing to the output buffer.
</p>
<table summary="Runtime auto-sanitization" cellpadding=4 cellspacing=0 border=1>
  <tr><th>Content</th><th>Trusted</th><th>Context</th><th>Sanitization function</th></tr>
  <tr><td><code>&lt;ul&gt;</code><td>Yes<td>PCDATA<td>none</tr>
  <tr><td><code>&lt;li onclick=&quot;alert(&apos;&gt;</code><td>Yes<td>PCDATA<td>none</tr>
  <tr><td><code>foo</code><td>No<td>JS string<td>escapeJSString</tr>
  <tr><td><code>&apos;)&quot;&gt;</code><td>Yes<td>JS string<td>none</tr>
  <tr><td><code>foo</code><td>No<td>PCDATA<td>escapeHTML</tr>
  <tr><td><code>&lt;li onclick=&quot;alert(&apos;&gt;</code><td>Yes<td>PCDATA<td>none</tr>
  <tr><td><code>&lt;script&gt;doEvil()&lt;/script&gt;</code><td>No<td>JS string<td>escapeJSString</tr>
  <tr><td><code>&apos;)&quot;&gt;</code><td>Yes<td>JS string<td>none</tr>
  <tr><td><code>&lt;script&gt;doEvil()&lt;/script&gt;</code><td>No<td>PCDATA<td>escapeHTML</tr>
  <tr><td><code>&lt;/ul&gt;</code><td>Yes<td>PCDATA<td>none</tr>
</table>

<p>
This works, and with a hand-tuned C parser has been deployed successfully on
<a href="http://google-ctemplate.googlecode.com/svn/trunk/doc/auto_escape.html">CTemplates</a>
and <a href="http://www.clearsilver.net/">ClearSilver</a>.
</p>

<p>
Writing a highly tuned parser in JavaScript though is difficult so implementing this scheme
requires making a hard trade-off between flexibility and correctness and download-size/speed.
</p>

<p>
Our proposal is a factor of 4 faster than a runtime scheme implemented
in JavaScript and has no download size cost above and beyond the code
for the sanitization functions and the calls to them.
</p>

<p>
Even in languages for which there are efficient parser generators,
runtime approaches might suffer performance-wise.  The overhead for
the static approach is independent of the number of times a loop is
re-entered, so templates that take large array inputs might perform
worse with even a highly efficient runtime scheme.
</p>

<p>
Runtime sanitization does do more elegantly in at least one area though.
Dynamic tag and attribute names pose no problems to a runtime sanitizer.
Whereas our scheme has to filter attribute names so that
<code>$aname</code> cannot be <code>"onclick"</code> in
<code class=prettyprint>&lt;button {$aname}=&hellip;&gt;</code>, because a
static approach must decide that the beginning of the attribute value
is either a JavaScript context or some other context, a runtime approach
can take into account the actual value of <code>$aname</code>.
This is not a common problem, and our approach does handle many dynamic
attribute situations including:
<code class=prettyprint>&lt;button on{$handlerType}=&hellip;&gt;</code>.
</p>

<h3>Strawman IV: A purely static approach</h3>
<p>
We know of no purely static approaches, though they are possible.
A purely static approach is one that, like our proposal, infers contexts
at compile or load time, but does not take into account the runtime type
of the values that fill the data holes.
</p>

<p>
This approach has problems with over-escaping.  Existing systems often
use a mix of sanitization in-template and sanitization outside the template
in the front-end code that calls the template.
</p>

<p>
Our solution takes into account the runtime type of the values that
fill a hole.  If the runtime type marks the value as a known-safe
string of HTML, then a sanitization function can choose not to
re-escape, and instead normalize or do nothing.
</p>

<p>
See <a href="#caveats">caveats</a> for other problems that are
as equally applicable to pure static systems as to our proposal.
</p>

<h2>Definitions and Algorithms</h2>
<p>
This section is only relevant to implementors, testers, and others who want
to understand the implementation.
Everyone else, including web application developers, can ignore it.
</p>

<p>
At a high level, the type system defines four things which are
expanded upon below:
</p>
<ol>
  <li>An initial start context for a public template.  Typically
    <code>HTML_PCDATA</code>.
  <li>A context propagation algorithm which takes a chunk of literal
    text from the template and the context at its start and returns
    the context at its end.  <code>(context * string) &rarr; context</code>.
  <li>An algorithm that chooses a sanitization function for a data hole.
    It takes the context before the hole and returns a sanitization
    function and the context after the hole.
    <code>context &rarr; ((&alpha; &rarr; string) * context)</code>.
    If data holes have statically available type info, then the type
    could be taken into account : <code>(context * type) &rarr;
    ((&alpha; &rarr; string) * context)</code>.
  <li>A context join operator that takes the contexts at the end of
    branches and yields the context after the branches have joined.
    This is used to determine the context at the end of a conditional
    <code>{if}</code> by joining the context at the end of the
    then-branch with the context at the end of the else-branch.  It is
    also used with loops, where (unless proven otherwise) we have to
    join the context at the start (loop never entered) with a context
    once through, with a steady state context for many repetitions.
    <code>context list &rarr; context</code>
</ol>

<p>
By contrast, the runtime auto-sanitization scheme described in
strawman III has the same initial context, the same context propagation
operator, no context join operator and uses a slightly differently
shaped sanitization function chooser :
<code>context &rarr; (&alpha; &rarr; (string * context))</code>.
</p>

<h3>Contexts</h3>
<p>
A context captures the state of the parser in a combined HTML/CSS/JS
lexical grammar.  It is composed of a number of fields which pack
into 2 bytes with room to spare:
</p>
<ul>
  <li>State &mdash; a coarse parser state that distinguishes between
    CDATA/RCDATA/PCDATA and attributes in HTML, comments, strings, and
    regular expressions in JavaScript; and between comments, strings,
    and URLs in CSS.</li>
  <li>Element Type &mdash; when in an HTML tag (between
    <code>&lt;</code> and <code>&gt;</code>), keeps track of whether
    the tag body is PCDATA, RCDATA, or CDATA; and once in an RCDATA or
    CDATA tag body, used to keep track of the expected end tag,
    e.g. inside a <code>&lt;script&gt;</code> body we have to find a
    <code>&lt;/script&gt;</code> tag, but should ignore any apparent
    <code>&lt;/style&gt;</code> tags.</li>
  <li>Attribute type &mdash;
    distinguishes between JS attributes (<code>onclick</code>,
    etc.), <code>style</code> attributes, URL attributes
    (<code>href</code>, etc.), and others.</li>
  <li>Attribute end delimiter &mdash; indicates the termination
    condition for the attribute value: double quoted, single
    quoted, unquoted, or none.</li>
  <li>JavaScript following slash &mdash;
    explains what to do with a <code>/</code> that does not start a
    comment: enter a regular expression literal, or a division
    operator, or fail with an error message due to ambiguity from
    context joining.</li>
  <li>URI part &mdash; the part of the URI that we're
    in: the start, path, query, fragment, or an ambiguous part due to
    context joining.</li>
</ul>

<p>
Contexts support two operators: join and &epsilon;-commit.
</p>

<p>
The join operator produces the context at the end of a condition,
loop, switch, or other flow control construct.  This sometimes
introduces an ambiguity.  In the template:
</p>
<pre class="prettyprint">
&lt;form action="<span class=nocode>{if $tgt}</span>/{$name}/handle?tgt={$tgt}<span class=nocode>{else}</span>/{$name}/default<span class=nocode>{/if}</span><span class=nocode>&uarr;</span>"&gt;Hello {$name}&hellip;
</pre>
<p>
One branch ends in the query portion of a URI, and one ends outside
it.  If there were a data hole at the <tt>&uarr;</tt>, then we would
not be able to determine an appropriate sanitization function for
it&dagger;.  So context joining often introduces just enough
ambiguity, by using do-not-know values for fields, and in the common
case, we later reach a point where we discard that info.  In the URI
case, if there were a <code>#</code> character at the
<tt>&uarr;</tt> we can reliably transition into a URI fragment
context, and in any case, the end of the attribute moots the
question.
</p>

<p>
The &epsilon;-commit operator is used when we see a data hole.  In
some cases, we introduce parser states to delay decision making.
In the template fragment, <code class=prettyprint>&lt;a href=</code>,
we could see a quote character next, or space, or the start of an
unquoted value, or the end of the tag (implying empty href), or a data
hole specifying the start of an unquoted attribute value.
If the next construct is a data hole we need to commit to it being
an unquoted attribute.  The &epsilon;-commit operator in this case
goes from an HTML_BEFORE_ATTRIBUTE_VALUE state with an attribute
end delimiter of NONE to a state appropriate to the value type
(e.g. JS for an <code>onclick</code> attribute) with an
attribute end delimiter of SPACE_OR_TAG_END.
</p>

<p>
The precise details of both these operators were determined empirically
to come up with the simplest semantics that handles cases found in
real code that web developers do not consider to be badly written or
confusing.
</p>

<p>
<small>&dagger; &mdash; This could be fixed by migrating the
problematic data hole and the code leading up to it into each branch,
but this is tricky to do across template boundaries and has not proven
to be necessary for the codebase we migrated.</small>
</p>

<div class="fullversiononly">
<h3>Grammar</h3>
<p>
The context propagation algorithm uses a combined HTML/CSS and JS
lexical grammar described below.  Click on non-terminal productions
for more detail.
</p>

    <script src="//html-railroad-diagram.googlecode.com/svn/trunk/src/railroad.js"></script>

    <script>
    function nonTerminal(name) {
      if (/\W/.test(name)) { throw new Error(name); }
      var target = document.getElementById(name);
      if (target) {
        return '&lt;<a href="#' + name + '"' + (
            isPopup(target) ? ' onclick="showPopup(&quot;' + name + '&quot;)"' : '')
            + '>' + name + '<\/a>&gt;';
      } else {
        return '&lt;' + name + '&gt;';
      }
    }

    function grammar(id, grammar) {
      var stats = {};
      var railroadContainer = document.getElementById(id);
      railroad.appendToDOM(grammar, railroadContainer, stats);
      railroadContainer.style.width = stats.width + 'px';
      railroadContainer.style.height = stats.height + 'px';
    }

    function isPopup(el) {
      return /\bpopup\b/.test(el.className);
    }

    function showPopup(id) {
      var target = document.getElementById(id);
      var popupPane = document.getElementById('popup-pane');
      popupPane.innerHTML = '<button id="close-button" onclick="hidePopup()">X</button>' + target.innerHTML;
      popupPane.style.display = '';
    }

    function hidePopup() {
      var popupPane = document.getElementById('popup-pane');
      popupPane.style.display = 'none';
    }
    </script>
    <style>
    .popup { display: none }
    #popup-pane > h4:nth-of-type(1) { margin-top: 0 }
    #popup-pane > p:last-of-type { margin-bottom: 0 }
    @media print {
      .popup { display: block !important }
      #popup-pane { display: none !important }
    }
    #popup-pane {
      font-size: 75%;
      position: fixed;
      top: 2px; right: 2px;
      width: 32em;
      border: 1px dotted black;
      padding: .5em;
      background-color: #fff
    }
    #close-button {
      position: absolute;
      top: 2px; right: 2px;
    }
    </style>


    <h4 id=HTML>HTML</h4>
    <div id="html-railroad"></div>

    <h4 id=Attributes>Attributes</h4>
    <div id="attributes-railroad"></div>

    <h4 id=JS>JS</h4>
    <div id="js-railroad"></div>

    <h4 id=CSS>CSS</h4>
    <div id="css-railroad"></div>

    <h4 id=URI>URI</h4>
    <div id="uri-railroad"></div>

    <div id=DynamicText class="popup">
      <h4>DynamicText</h4>
      Converts plain text to HTML by entity encoding unless it's type indicates it is known safe HTML.
      <ul>
        <li>`<kbd>I &lt;3 ponies</kbd>` &rarr; `<kbd>I &amp;lt;3 ponies</kbd>`</li>
        <li><code>new SanitizedHtml('&lt;b&gt;Hello, World&lt;/b&gt;')</code> &rarr; `<kbd>&lt;b&gt;Hello, World!&lt;/b&gt;</kbd>`
      </ul>

      <p>The first case is handled by encoding all PCDATA special
      characters (<kbd>&lt;</kbd>, <kbd>&gt;</kbd>, and
      <kbd>&amp;</kbd>) as HTML entities (<kbd>&amp;lt;</kbd>,
      <kbd>&amp;gt;</kbd>, and <kbd>&amp;amp;</kbd>).  Other
      code-points may be escaped, but need not be.
      <p>
      In the second case, the safe HTML is emitted as is.  It must be
      a mixed group of complete tags and text nodes such that there
      exists a safe template that could have produced it starting from
      an HTML PCDATA context and ending in the same context, or there
      exists a safe HTML sanitizer that could have produced it.
    </div>

    <div id=DynamicRcdata class="popup">
      <h4>DynamicRcdata</h4>
      Converts plain text to HTML by entity encoding unless it's type indicates it is known safe HTML.
      <ul>
        <li>`<kbd>I &lt;3 ponies</kbd>` &rarr; `<kbd>I &amp;lt;3 ponies</kbd>`</li>
        <li><code>new SanitizedHtml('&lt;b&gt;Hello, World&lt;/b&gt;')</code> &rarr; `<kbd>&amp;lt;b&amp;gt;Hello, World!&amp;lt;/b&amp;gt;</kbd>`
      </ul>

      <p>The first case is handled by encoding all RCDATA special
      characters (<kbd>&lt;</kbd>, <kbd>&gt;</kbd>, and
      <kbd>&amp;</kbd>) as HTML entities (<kbd>&amp;lt;</kbd>,
      <kbd>&amp;gt;</kbd>, and <kbd>&amp;amp;</kbd>).  Other
      code-points may be escaped, but need not be.
      <p>
      In the second case, the safe HTML is normalized.  All the HTML
      special characters are escaped except for ampersands
      (<kbd>&</kbd>), which are left as-is.  Since all RCDATA end tags
      contain `<kbd>&lt;</kbd>`, and `<kbd>&lt;</kbd>` is escaped to a
      string that does not contain it, and no other code units are
      escaped to a string that contains it, no safe HTML chunk can
      cause premature ending of an RCDATA tag.  This means that the
      safety of the odd but valid Soy template
      <code>&lt;textarea&gt;{$foo}&lt;script&gt;alert('Keystone&nbsp;kop');&lt;/script&gt;&lt;/textarea&gt;</code>
      will not violate the structure security goal or unauthored code
      security goal even when a chunk of safe HTML contains an RCDATA
      end tag like <code>&lt;/textarea&gt;</code>.
    </div>

    <div id=DynamicTagName class="popup">
      <h4>DynamicTagName</h4>
      Allows through parts of non-CDATA, non-RCDATA tag names.
      So the Soy <code>&lt;h{$headerLevel}&gt;</code> can be used to
      generate <code>&lt;h1&gt;</code>, <code>&lt;h2&gt;</code>,
      &hellip;

      <p>To avoid problems where a tag name might be combined with a
      static part to form <code>script</code>, <code>style</code>, or
      another <code>CDATA</code> or <code>RCDATA</code> tag, we impose
      the following restrictions:
      <ul>
        <li>must contain only ASCII letters, digits, dashes and colons; and</li>
        <li>must<ul>
          <li>contain a colon (a namespace), or
          <li>contain a digit, or
          <li>be the full name (case-insensitive) of a non-RCDATA, non-CDATA HTML element.
        </ul>
      </ul>
    </div>

    <div id=DynamicAttrName class="popup">
      <h4>DynamicAttrName</h4>
      Allows through parts of a non-special attribute name.
      <ul>
        <li>`<kbd>checked</kbd>` &rarr; `<kbd>checked</kbd>`</li>
        <li>`<kbd>&lt;script&gt;alert(pwned)&lt;/script&gt;</kbd>` &rarr; <i>error</i></li>
      </ul>

      <p>TODO: scheme to avoid concatenation from producing
      <code>on</code>*, <code>style</code>, <code>href</code>, etc.
    </div>

    <div id=DynamicAttrValue class="popup">
      <h4>DynamicAttrValue</h4>
      Converts plain text to HTML by entity encoding so it can be embedded in an HTML attribute.
      If embedded in a quoteless attribute, then also encodes spaces.
      <p>
      If the result is known safe HTML, strips tags so that the Soy
      <code>&lt;abbr&nbsp;title="{$longDesc}"&gt;{$shortDesc}&lt;/abbr&gt;</code> works
      even when both <code>$longDesc</code> and
      <code>$shortDesc</code> are snippets of sanitized HTML.

      <ul>
        <li>`<kbd>I <3 ponies</kbd>` &rarr; `<kbd>I &amp;lt;3 ponies</kbd>`</li>
        <li><code>new SanitizedHtml('&lt;b&gt;Hello, World&lt;/b&gt;')</code> &rarr; `<kbd>Hello, World!</kbd>`
      </ul>

      <p>The first case is handled by encoding all HTML special
      characters including quotes (<kbd>&lt;</kbd>, <kbd>&gt;</kbd>,
      <kbd>&amp;</kbd>, <kbd>&quot;</kbd>, <kbd>'</kbd>, and
      <kbd>=</kbd>) as HTML entities (<kbd>&amp;lt;</kbd>,
      <kbd>&amp;gt;</kbd>, <kbd>&amp;amp;</kbd>,
      <kbd>&amp;quot;</kbd>, and <kbd>&amp;#34;</kbd>,
      <kbd>&amp;#61;</kbd>).
      <p>The second case is handled by stripping HTML tags and
      comments from the safe HTML, and then normalizing it by
      applying the same escaping scheme as for the first case, but
      without encoding ampersands (<kbd>&amp;</kbd>).
      <p>For both cases, when the HTML attribute is not quoted, we
      additionally have to quote all codepoints that would signal the
      end of an HTML attribute, including a number of space and
      control characters.  This set was derived empirically, and
      includes the backtick (<kbd>`</kbd>) which can be used as a
      quoting character on some versions of IE.
    </div>

    <div id=DynamicJsString class="popup">
      <h4>DynamicJsString</h4>
      Escapes plain text so it can be incorporated into part of a JS
      string literal by escaping special characters, e.g. newline
      &rarr; <code>\n</code>.
      <ul>
        <li>`<kbd>John "The Anonymous" Doe</kbd>` &rarr; `<kbd>John \"The Anonymous\" Doe</kbd>`</li>
      </ul>

      <p>We escape dynamic JS strings using the following table:
      <table>
        <tr><th>Codepoint<th>Glyph<th>Escape</tr>
        <tr><td>000A<sub>16</sub><td><td><kbd>\n</kbd></tr>
        <tr><td>000D<sub>16</sub><td><td><kbd>\r</kbd></tr>
        <tr><td>0022<sub>16</sub><td><kbd>&quot;</kbd><td><kbd>\u0022</kbd></tr>
        <tr><td>0027<sub>16</sub><td><kbd>&#39;</kbd><td><kbd>\u0027</kbd></tr>
        <tr><td>002F<sub>16</sub><td><kbd>/</kbd><td><kbd>\/</kbd></tr>
        <tr><td>003C<sub>16</sub><td><kbd>&lt;</kbd><td><kbd>\u003C</kbd></tr>
        <tr><td>003E<sub>16</sub><td><kbd>&gt;</kbd><td><kbd>\u003E</kbd></tr>
        <tr><td>005C<sub>16</sub><td><kbd>\</kbd><td><kbd>\\</kbd></tr>
        <tr><td>2028<sub>16</sub><td><td><kbd>\u2028</kbd></tr>
        <tr><td>2029<sub>16</sub><td><td><kbd>\u2029</kbd></tr>
      </table>
      <p>These escapes prevent premature string closing, since all JS
      quote characters are encoded to a sequence that does not contain
      a quote character and no other codepoint is encoded to a
      sequence containing a quote character.  This prevents additional
      JS syntax errors by properly encoding all JS newline codepoints.
      It preserves structure by encoding any sequences that would end
      a CDATA tag, CDATA section, escaping text span, or quoted HTML
      attribute value.  The output can be embedded in an HTML
      attribute value by additionally escaping <kbd>&amp;</kbd> to
      <kbd>\u0026</kbd>.  In the case of unquoted HTML attribute
      values, just escaping ampersands is not sufficient ; the output
      needs to be HTML entity escaped per
      <a href="#DynamicAttrValue" onclick="showPopup('DynamicAttrValue')">DynamicAttrValue</a>.
    </div>

    <div id=DynamicRegExp class="popup">
      <h4>DynamicRegExp</h4>
      <p>
      Like <a onclick="showPopup(&quot;DynamicJsString&quot;)" href="#DynamicJsString">DynamicJsString</a>,
      but additionally escapes characters special in regexp like
      <kbd>?</kbd> and <kbd>*</kbd>.

      <ul>
        <li>`<kbd>John "The Anonymous" Doe + 1</kbd>` &rarr; `<kbd>John \"The Anonymous\" Doe \+ 1</kbd>`</li>
      </ul>
    </div>

    <div id=DynamicJsValue class="popup">
      <h4>DynamicJsValue</h4>

      Quotes strings and encodes them like
      <a onclick="showPopup(&quot;DynamicJsString&quot;)" href="#DynamicJsString">DynamicJsString</a>,
      puts spaces around boolean, <tt>null</tt>, and numeric values.

      <ul>
        <li>`<kbd>John "The Anonymous" Doe + 1</kbd>` &rarr; `<kbd>"John \"The Anonymous\" Doe + 1"</kbd>`</li>
        <li>`<kbd>42</kbd>` &rarr; `<kbd> 42 </kbd>`</li>
        <li>`<kbd>false</kbd>` &rarr; `<kbd> false </kbd>`</li>
      </ul>

      <p>Putting spaces around non-string values makes sure that they
      will be separate tokens but will not introduce a function call
      in the case of the Soy template
      <pre>
      <code>var f = function () {}  // Missing semicolon.
      {$myBoolean} && sideEffect();</code></pre>
      where due to semicolon insertion, adding parentheses would cause
      the template to produce the equivalent of
      <pre>
      <code>var f = ((function () {})(false)) && sideEffect();</code></pre>
      given <code>{ myBoolean: false }</code>.
    </div>

    <div id=DynamicCssString class="popup">
      <h4>DynamicCssString</h4>
      Escapes plain text so it can be incorporated into part of a CSS
      string literal by escaping special characters, e.g. newline
      &rarr; <code>\10 </code>.
      <ul>
        <li>`<kbd>John "The Anonymous" Doe</kbd>` &rarr; `<kbd>John \22 The Anonymous\22  Doe</kbd>`</li>
      </ul>
      <p>We encode <b>all</b> CSS special characters using CSS hex
      escaping.  CSS hex escaping allows an escape to be followed
      optionally by a space or tab character so that an escape may be
      followed by an unescaped hex digit.  We always emit a following
      space.
      <p>We aggressively encode all CSS special characters to prevent unspecified
      <a href="http://www.w3.org/TR/css3-syntax/#error">CSS error recovery</a>
      from restarting parsing inside quoted strings.
      <blockquote>
      <h4>9.2.1. Error conditions</h4>

      <p>In general, this document does not specify error handling
      behavior for user agents (e.g., how they behave when they cannot
      find a resource designated by a URI).

      <p>However, user agents must observe the rules for handling parsing errors.

      <p>Since user agents may vary in how they handle error
      conditions, authors and users must not rely on specific error
      recovery behavior.
      </blockquote>

      <p>We also escape both angle brackets (<kbd>&lt;</kbd> and
      <kbd>&gt;</kbd>) (which is already a CSS special) so that HTML
      escaping text spans, CDATA sections, CDATA end tags, etc. cannot
      be introduced into the middle of CSS strings.
    </div>

    <div id=DynamicCssQuantityOrKeywordOrName class="popup">
      <h4>DynamicCssQuantityOrKeywordOrName</h4>
      Allows a CSS keyword, quantity, or ID or class name through, but filter content containing special characters.
      Some use cases:
      <ul>
        <li><code>color: #{$hashColor}</code>
        <li><code>color: {$colorName}</code>
        <li><code>border-{$rtlLeft}: &hellip; /* left for English, right for Arabic */</code>
        <li><code>div.{$className} { &hellip; }</code></li>
        <li><code>width: ${width}{$widthUnits}</code></li>
      </ul>

      Some example values:
      <ul>
        <li>`<kbd>24px</kbd>` &rarr; `<kbd>24px</kbd>`</li>
        <li>`<kbd>left</kbd>` &rarr; `<kbd>left</kbd>`</li>
        <li>`<kbd>background</kbd>` &rarr; `<kbd>background</kbd>`</li>
        <li>`<kbd>expression</kbd>` &rarr; <i>error</i>
      </ul>

      <p>TODO: explain the allowed set and its derivation.</p>
    </div>

    <div id=DynamicSchemeFilteredUriPart class="popup">
      <h4>DynamicSchemeFilteredUriPart</h4>

      <p>
      Whitelists a protocol if present to prevent code execution via
      <code>javascript:&hellip;</code>, and normalizes the URI
      (encoding all unencoded HTML special characters, quotes, spaces,
      and parentheses) so it can be embedded.  E.g. `<kbd>&quot;</kbd>`
      &rarr; <kbd>%22</kbd>.

      <p>
      URI normalization percent escapes all codepoints escaped by
      <a href="#DynamicQueryPart" onclick="showPopup('DynamicQueryPart')">
      DynamicQueryPart</a> except for the percent character (<kbd>%</kbd>).

      <p>
      TODO: Explain the filter details and their derivation.
    </div>

    <div id=DynamicQueryPart class="popup">
      <h4>DynamicQueryPart</h4>

      <p>Encodes all characters that are special or disallowed in a URI.

      <p>We encode all codepoints encoded by
      <code>encodeURIComponent</code> making the same assumption that
      the URL is UTF-8 encoded.

      <p>Over <code>encodeURIComponent</code>, we additionally encode
      single quotes (<kbd>'</kbd>) and parentheses(<kbd>(</kbd> and
      <kbd>)</kbd>) so that the result can be safely embedded in single
      quoted HTML attributes and in single quoted and unquoted CSS
      <code>url(&hellip;)</code> constructs.  Note that applying an
      extra level of CSS escaping using <code>\27 </code> style escapes is
      not an option since IE (for interoperability with DOS file paths?)
      does not interpret <code>\</code> as the beginning of an escape when
      it appears inside a <code>url(&hellip;)</code>.

      <p>Each of these characters is significant in a URI as specified
      in RFC 3986:
      <blockquote>
      <h4><a href="http://www.apps.ietf.org/rfc/rfc3986.html#sec-2.2" title="RFC 3986 2.2">2.2</a> Reserved Characters</h4>
      <pre>sub-delims  = "!" / "$" / "&" / <u>"'" / "(" / ")"</u></pre>
      </blockquote>

      so escaping them is technically not semantics preserving, but
      encoding them is safe for all schemes that commonly appear in
      HTML because those codepoints only appear in the obsolete mark
      productions.

      <blockquote>
      <h4><a href="http://www.apps.ietf.org/rfc/rfc3986.html#sec-D.2" title="RFC 3986 D.2">D.2</a> Modifications</h4>

      <p>The ad-hoc BNF syntax of RFC 2396 has been replaced with the
      ABNF of [RFC2234]. This change required all rule names that
      formerly included underscore characters to be renamed with a
      dash instead. In addition, a number of syntax rules have been
      eliminated or simplified to make the overall grammar more
      comprehensible. Specifications that refer to the obsolete
      grammar rules may be understood by replacing those rules
      according to the following table:

      &hellip;

      <pre>mark    "-" / "_" / "." / "!" / "~" / "*" / <u>"'" / "(" / ")"</u></pre>
      </blockquote>
    </div>

    <div id=DynamicUriPart class="popup">
      <h4>DynamicUriPart</h4>

      <p>
      Normalizes the URI like
      <a onclick="showPopup(&quot;DynamicSchemeFilteredUriPart&quot;)" href="#DynamicSchemeFilteredUriPart">URI normalization</a>
      so that an already encoded path or fragment can be emitted
      inline but does not filter since a protocol part cannot appear
      here.
    </div>

    <div id="popup-pane" style="display: none"></div>

    <script>(function () {

var any = railroad.any,
    each = railroad.each,
    many = railroad.many,
    maybe = railroad.maybe,
    or = railroad.or;

grammar('html-railroad',
    any(or(
        each('`<tt>&lt;script</tt>`', nonTerminal('Attributes'), '`<tt>&gt;</tt>`', nonTerminal('JS'), '`<tt>&lt;/script&gt;</tt>`'),
        each('`<tt>&lt;style</tt>`', nonTerminal('Attributes'), '`<tt>&gt;</tt>`', nonTerminal('CSS'), '`<tt>&lt;/style&gt;</tt>`'),
        each('`<tt>&lt;textarea</tt>`', nonTerminal('Attributes'), '`<tt>&gt;</tt>`', any(or(nonTerminal('StaticText'), nonTerminal('DynamicRcdata'))), '`<tt>&lt;/textarea&gt;</tt>`'),
        '&hellip;',
        each('`<tt>&lt;</tt>`', many(or(nonTerminal('StaticTagName'), nonTerminal('DynamicTagName'))), nonTerminal('Attributes'), '`<tt>&gt;</tt>`'),
        each('`<tt>&lt;/</tt>`', many(or(nonTerminal('StaticTagName'), nonTerminal('DynamicTagName'))), '`<tt>&gt;</tt>`'),
        nonTerminal('StaticText'),
        nonTerminal('DynamicText')
        )));

grammar('attributes-railroad',
        each(
            '`<tt>&nbsp;</tt>`',
            or(
                each(
                    '`<tt>on</tt>`',
                    or(
                        nonTerminal('StaticAttrName'),
                        nonTerminal('DynamicAttrName')),
                    maybe(
                        each(
                            '`<tt>=</tt>`',
                            or(
                                each(
                                    '`<tt>"</tt>`',
                                    nonTerminal('JS'),
                                    '`<tt>"</tt>`'),
                                each(
                                    '`<tt>\'</tt>`',
                                    nonTerminal('JS'),
                                    '`<tt>\'</tt>`'),
                                nonTerminal('JS'))))),
                each(
                    '`<tt>style</tt>`',
                    maybe(
                        each(
                            '`<tt>=</tt>`',
                            or(
                                each(
                                    '`<tt>"</tt>`',
                                    nonTerminal('CSS'),
                                    '`<tt>"</tt>`'),
                                each(
                                    '`<tt>\'</tt>`',
                                    nonTerminal('CSS'),
                                    '`<tt>\'</tt>`'),
                                nonTerminal('CSS'))))),
                each(
                    or(
                        '`<tt>href</tt>`',
                        '`<tt>src</tt>`',
                        '&hellip;'),
                    maybe(
                        each(
                            '`<tt>=</tt>`',
                            or(
                                each(
                                    '`<tt>"</tt>`',
                                    nonTerminal('URI'),
                                    '`<tt>"</tt>`'),
                                each(
                                    '`<tt>\'</tt>`',
                                    nonTerminal('URI'),
                                    '`<tt>\'</tt>`'),
                                nonTerminal('URI'))))),
                each(
                    or(
                        nonTerminal('StaticAttrName'),
                        nonTerminal('DynamicAttrName')),
                    maybe(
                        each(
                            '`<tt>=</tt>`',
                            or(
                                each(
                                    '`<tt>"</tt>`',
                                    any(or(nonTerminal('StaticAttrValue'), nonTerminal('DynamicAttrValue'))),
                                    '`<tt>"</tt>`'),
                                each(
                                    '`<tt>\'</tt>`',
                                    any(or(nonTerminal('StaticAttrValue'), nonTerminal('DynamicAttrValue'))),
                                    '`<tt>\'</tt>`'),
                                any(or(nonTerminal('StaticAttrValue'), nonTerminal('DynamicAttrValue')))))))
        )));

grammar('js-railroad',
    any(or(
        each('`<tt>"</tt>`', any(or(nonTerminal('StaticJsString'), nonTerminal('DynamicJsString'))), '`<tt>"</tt>`'),
        each('`<tt>\'</tt>`', any(or(nonTerminal('StaticJsString'), nonTerminal('DynamicJsString'))), '`<tt>\'</tt>`'),
        each('`<tt>/*</tt>`', nonTerminal('BlockCommentBody'), '`<tt>*/</tt>`'),
        each('`<tt>//</tt>`', nonTerminal('LineCommentBody')),
        each('<nobr style="border:1px solid black; border-radius: 4px; padding:2px">look-behind(RegExp-preceder)</nobr>',
             '`<tt>/</tt>`',
             many(or(
                 nonTerminal('StaticRegExp'),
                 nonTerminal('DynamicRegExp'),
                 each('`<tt>[</tt>`',
                      many(or(
                          nonTerminal('StaticRegExp'),
                          nonTerminal('DynamicRegExp'))),
                      '`<tt>]</tt>`'))),
             '`<tt>/</tt>`'),
        each('<nobr style="border:1px solid black; border-radius: 4px; padding:2px">look-behind(div-preceder)</nobr>',
             '`<tt>/</tt>`'),
        nonTerminal('DynamicJsValue'),
        nonTerminal('StaticJsSpaceNumberBooleanKeywordIdentifierOrOperator')
    )));

grammar('css-railroad',
    any(or(
        each('`<tt>"</tt>`', any(or(nonTerminal('StaticCssString'), nonTerminal('DynamicCssString'))), '`<tt>"</tt>`'),
        each('`<tt>\'</tt>`', any(or(nonTerminal('StaticCssString'), nonTerminal('DynamicCssString'))), '`<tt>\'</tt>`'),
        each('`<tt>/*</tt>`', nonTerminal('BlockCommentBody'), '`<tt>*/</tt>`'),
        each('`<tt>url(\"</tt>`', nonTerminal('URI'), '`<tt>\")</tt>`'),
        each('`<tt>url(\'</tt>`', nonTerminal('URI'), '`<tt>\')</tt>`'),
        each('`<tt>url(</tt>`', nonTerminal('URI'), '`<tt>)</tt>`'),
        nonTerminal('DynamicCssQuantityOrKeywordOrName'),
        nonTerminal('StaticCssQuantityKeywordNamePunctuationOrSpace')
    )));

grammar('uri-railroad',
    each(
        maybe(or(nonTerminal('StaticScheme'), nonTerminal('DynamicSchemeFilteredUriPart'))),
        maybe(
            each(
                nonTerminal('StaticUriPart'),
                any(or(nonTerminal('DynamicUriPart'), nonTerminal('StaticUriPart'))))),
        maybe(each('`<tt>?</tt>`', any(or(nonTerminal('DynamicQueryPart'), nonTerminal('StaticQueryPart'))))),
        maybe(each('`<tt>#</tt>`', any(or(nonTerminal('DynamicUriPart'), nonTerminal('StaticUriPart')))))));

})()</script>
    <script>
    (function () {
      if (/^#\w+$/.test(location.hash)) {
        var id = location.hash.substring(1);
        if (isPopup(document.getElementById(id))) {
          showPopup(id);
        }
      }
    })();
    </script>
</div>

<h3>Context Propagation</h3>
<p>
The context propagation algorithm uniquely determines the context at
every data hole so that a later pass may chose a sanitization
function for each hole.
The algorithm operates at two level, one on the graph of templates,
and another individually within templates.
The first deals with identifying the minimal set of templates that
need to be processed, and might clone templates to deal with templates
that are called in multiple different contexts.
</p>

<p>
The template context propagation algorithm uses an inference object
which is implemented as a set of nested maps and a pointer to a parent
inference object.  This allows us to speculatively type a template
sub-graph, and when we have a consistent view of types, we can
collapse our conclusions into the parent by simply copying maps from
children to parent.  The maps include maps from holes to start
contexts, from templates to end contexts used to type calls.
</p>

<pre class="prettyprint">
def autosanitize(templates):
  inferences = Inferences()
  for template in templates:
    if inferences.getEndContext(template) is not None: continue # already done
    if template.is_public() or template.is_contextually_autosanitized():
      # By exploring the call graph from only public templates, ones
      # that can be invoked by front-end code, we do not trigger error checks for
      # parts of the code-base that don't yet use contextual
      # auto-sanitization, easing migration.
      compute_end_context(template, inferences, start_context=HTML_PCDATA&dagger;)
  return inferences
</pre>

<p>
That algorithm delegates all the hard work to another algorithm below that
examines the template graph reachable from one particular top-level
template.
</p>

<pre class="prettyprint">
def compute_end_context(template, inferences, start_context):
  # We need to choose an end context before typing the body to avoid
  # infinite regression for recursive templates.

  # Start with the optimistic assumption that the template ends in the
  # same context in which it starts.
  # Empirically, less than 0.2% of templates in our sample violate
  # this assumption.
  # The ones that do tend to be some of the gnarliest code that
  # template authors would rather not refactor.
  optimistic_assumption_1 = Inferences(parent=inferences)
  optimistic_assumption_1.template_end_contexts[template] = start_context
  end_context = propagate_context(
      template.children, start_context, optimistic_assumption_1)
  if start_context == end_context:  # Our optimistic assumption was warranted.
    optimistic_assumption_1.commit_into_parent()
    return end_context

  # Otherwise, assume that the end_context above is the end_context
  # and check that we have reached a fixed point.
  optimistic_assumption_2 = Inferences(parent=inferences)
  optimistic_assumption_2.template_end_contexts[template] = end_context
  end_context_fixed_point = propagate_context(
      template.body, start_context, optimistic_assumption_2)
  if end_context_fixed_point == end_context:  # We have a fixed point.  Phew!
    optimistic_assumption_2.commit_into_parent()
    return end_context_fixed_point

  # We could try other strategies to generate optimistic assumptions, but
  # we have not seen a need in real template code.
  raise Error(...)
</pre>

<p>
Thus far, we have done nothing that is particular to the syntax
templating language itself.  Different languages have different
semantics around parameter passing, and provide different flow control
constructs.  The algorithm below is an example for one that deals with
a simple template language that provides calls, conditions, chunks of
static template text, and expression interpolations which fill data
holes.  On a call, it may recurse to the compute end context algorithm
above, which is how we lazily explore the portion of the template call
graph needed.
</p>

<pre class=prettyprint>
def propagate_context(parse_tree_nodes, context, inferences):
  for parse_tree_node in parse_tree_nodes:
    if is_safe_text_node(parse_tree_node):
      context = apply_html_grammar(parse_tree_node.safe_text, context)
    elif is_data_hole(parse_tree_node):
      context = &epsilon_commit(context)  # see definition above
      inferences.context_for_data_hole[node] = context
      context = &hellip;  # compute context after hole.
    elif is_conditional(parse_tree_node):
      if_context = propagate_context(parse_tree_node.if_branch, context, inferences)
      else_context = propagate_context(parse_tree_node.else_branch, context, inferences)
      context = context_join(if_branch, else_branch)
    elif is_call_node(parse_tree_node):
      output_context = None
      # possible_callees comes up with the templates this might be calling,
      # and may clone templates if they are called in multiple different contexts.
      # Most template languages have static call graphs, so in practice, there is
      # exactly one possible callee.
      for possible_callee in possible_callees_of(parse_tree_node, context):
        if possible_callee not in inferences.template_end_contexts:
          context_after_call = compute_end_context(possible_callee, inferences, context)
        else:
          context_after_call = inferences.template_end_contexts[possible_callee]
        if output_context is None:
          output_context = context_after_call
        else:
          # Since 99% of templates end in their start context, in practice,
          # this join does little.
          output_context = context_join(output_context, context_after_call)
      context = output_context
  return context
</pre>

<p><small>
&dagger; &mdash; We make the simplifying assumption that the start
context for all public templates is HTML_PCDATA.  Some templating
languages may be used in different contexts, and so this assumption
might not prove valid.  We could choose the starting context for
public templates based on some kind of annotation or naming convention
particular to the templating language.
</small></p>

<h3>Sanitization Functions</h3>
<p>
We define a suite of sanitization functions.  The table below
describes them briefly and the context in which they are used.  There
are significantly more than most manual escaping schemes.  As noted
above, most developers who don't work on parsers for HTML/CSS/JS have
a simplified mental model of the grammar which makes it difficult to
choose between this many options.  We have many sanitization functions
because we want to minimize template output size to minimize network
latency; having more sanitization functions lets us avoid escaping
common characters like spaces when safe.
<span class="fullversiononly">
The naming convention for sanitization function reflects the
<a href="#glossary-escaper">escaper</a>,
<a href="#glossary-filter">filter</a>, and
<a href="#glossary-normalizer">normalizer</a>
definitions from the glossary.
</span>
<span class="shortversiononly">
By convention, sanitization functions are split into broad
groups: escaping functions transform an input language (usually plain
text) to the output language, filters transform any input language to
the same string or to an innocuous string, and normalizers transform a
string in the input language to an output in the same language but
that is easier to embed in other languages.
</span>
</p>

<table summary="sanitization functions" cellpadding=4 cellpadding=0 border=1>
  <tr><td><code>escapeHTML</code></td>
    <td>HTML entity escapes plain text, and allows pre-saniized HTML
      content through unchanged</tr>
  <tr><td><code>normalizeHTML</code></td>
    <td>Normalizes HTML.  Same as HTML, but does not encode
      ampersands.</tr>
  <tr><td><code>{escape,normalize}HTMLRcdata</code></td>
    <td>Like <code>escapeHTML</code> but does not exempt pre-sanitized
      content since RCDATA
      <span class="fullversiononly">(<code>&lt;title&gt;</code> and
      <code>&lt;textarea&gt;</code>)</span> can't contain tags.</tr>
  <tr><td><code>{escape,normalize}HTMLAttribute</code></td>
    <td>Like <code>escapeHTML</code> but strips tags from
      pre-sanitized content.</tr>
  <tr><td><code>filterHtmlElementName</code></td>
    <td>Rejects any invalid element name or non PCDATA element.</tr>
  <tr><td><code>filterHtmlAttribName</code></td>
    <td>Rejects any invalid attribute name or attribute name that
      has JS, CSS, or URI content.</tr>
  <tr><td><code>{escape,normalize}URI</code></td>
    <td>Percent encodes
      <span class="fullversiononly"> (assuming UTF-8)</span>
      URI,HTML,JS,&amp;CSS
      special characters to allow safe embedding.
      <span class="fullversiononly">This
      means encoding parentheses and single quotes which should not be
      normalized according to RFC 3986, and is not valid for all
      non-hierarchical URI schemes, but the only productions using
      single quotes or parentheses are obsolete marker productions,
      and normalizing these characters is essential to safely
      embedding URIs in unquoted CSS <code>url(&hellip;)</code>
      and to make sure that CSS error recovery mode doesn't jump
      into the middle of a quoted string.</span></tr>
  <tr><td><code>filterNormalizeUri</code></td>
    <td>Like <code>normalizeUri</code> but rejects any input
      that has a protocol other than <code>http</code>,
      <code>https</code>, or <code>mailto</code>.</tr>
  <tr><td><code>{escape,normalize}JSStringChars</code></td>
    <td>Uses <code>\uABCD</code> style escapes for
      code-units special in HTML, JS, or conditional compilation.</tr>
  <tr><td><code>{escape,normalize}JSRegexChars</code></td>
    <td>Like <code>{escape,normalize}JSStringChars</code> but also
      escapes regular expression specials <span class="fullversiononly">
      such as <code>'$'</code></span>.</tr>
  <tr><td><code>{escape,normalize}JSValue</code></td>
    <td>Encodes booleans &amp; numbers wrapped in spaces, else quotes and escapes.</tr>
  <tr><td><code>escapeCSSStringChars</code></td>
    <td>Uses <code>\ABCD</code> style escapes to escape HTML
      and CSS special characters.</tr>
  <tr><td><code>filterCssIdentOrValue</code></td>
    <td>Allows <tt>class</tt>es, <tt>id</tt>s, property
      name parts for bidi, CSS keyword values,
      colors, &amp; quantities.</tr>
  <tr><td><code>noAutoescape</code></td>
    <td>Passes its input through unchanged.  This is an auditable
      exception to auto-sanitization.</tr>
</table>

<h3 id="sanitized_content_types">Sanitized Content Types</h3>
<p>
Sanitized content allows template users to pre-sanitize some content,
and allow approved structured content.
</p>

<p>
<code>new SanitizedContent('&lt;b&gt;Hello, World!&lt;/b&gt;')</code>
specifies a chunk of HTML that the creator asserts is safe to embed
in HTML PCDATA.
</p>

<p>
It is possible for misuse of this feature to violate all the safety
properties contextual auto-sanitization provides.
We assert that allowing this makes it easier to migrate code that
has no XSS safety net to a better place, and satisfies some
compelling use cases including
HTML translated into foreign languages by trusted translators, and
HTML from tag whitelisters, wiki-text-to-html converters, rich text editors.
But it needs to be used carefully.  Developers should:
</p>
<ul>
  <li>Don't roll your own escapers and deprecate ones in existing code.
    This does not apply to filters.  Filter early, and filter often.
  </li>
  <li>Put the sanitized content type constructor as close to the
    code that does the sanitization.</li>
  <li>Don't use tag or attribute black-lists.</li>
  <li>Be skeptical of "safe" HTML from a database.  This is
    a vector for SQL Injection to turn into XSS.
</ul>

<h2 id="caveats">Caveats</h2>
<p>
As noted above, (in the runtime contextual auto-sanitization strawman)
static approaches (including ours) cannot handle all possible uses of
dynamic attribute and element name.  These seem rare in real code, and
relatively easy to fix, but if necessary, a hybrid runtime/static
approach could address this problem.
</p>

<p>
Static approaches get into corner cases around zero-length untrusted
values.  For example, to preserve the
<a href="#code_effect_property">code effect property</a>, we need to
make sure that no untrusted value specifies a <code>javascript:</code>
or similar URL protocol.  In template code like
<code class=prettyprint>&lt;img src="{$x}{$y}"&gt;</code> we might
naively decide that it is sufficient to filter <code>$x</code> to make
sure that it specifies no protocol or an approved one.  But if
<code>$x</code> is the empty string, then <code>$y</code> might still
specify a dangerous protocol.  Alternatively <code>$x</code> might
specify <code>"javascript"</code> and <code>$y</code> start with a
colon.  This hole can be closed a number of ways, e.g.
<code>java<b>%73</b>cript:alert(1337)</code> is not a dangerous URL.
Similar problems arise with JavaScript regular expressions:
<code class=prettyprint>var myPattern = /{$x}/</code> where an empty
<code>$x</code> could turn the regular expression literal into a
line comment and there are similar special case fixes
(<code>/(?:)/</code> is not a comment).
But a general solution to empty strings would be a source
of considerable complexity.  Simply making sanitizer functions variadic
(<code>{$x}{$y}</code> &rarr; <code>{filterNormalizeUri($x, $y)}</code>)
will not suffice because the two interpolations might cross
template boundaries.
</p>

<p>
Our JavaScript parser is unsound.  JavaScript is a language that does
not have a regular lexical grammar (even ignoring conditional compilation)
because of the way it specifies whether a <code>/</code> starts a regular
expression or a division operator.
We use a scheme based on a draft JavaScript 1.9 grammar devised by
Waldemar Horwat that makes that decision based on the last non-comment
token.  This works well for all the code we've seen that people actually
write, and makes our approach feasible, but there is a known case where
it fails: <code>x++ /a/i</code> vs <code>x = ++/a/i</code>.
The second code snippet, while nonsensical, is valid JavaScript that our
scheme fails to handle correctly.
</p>

<p>
Our parser does not currently recognize HTML5
<a href="http://dev.w3.org/html5/markup/aria/syntax.html#escaping-text-span" title="Escaping Text Spans">escaping text spans</a>,
the regions inside <code>&lt;script&gt;</code> and
<code>&lt;style&gt;</code> bodies delimited by <code>&lt;!--</code>
and <code>--&gt;</code> that suppress end-tag processing.  This can be
fixed if a codebase seems to use them.  Our santization function
choices are designed to not produce content containing escaping text
span boundaries.
</p>

<p>
Our parser does not descend into HTML, CSS, or JS in <tt>data:</tt>
URLs.
We could but have not encountered the need in existing code.
</p>


<h2>Case Study</h2>
<p>
We studied 1035 templates that were migrated from an existing codebase
to use contextually sanitized templates.
Most of the templates were relatively small but totaled 21098 LOC and
783kB.  The compilation load time cost for these 1035 templates was
998339279 ns on a platform with 2 GB of RAM, an Intel 2.6 MHz
dual-core processor running Linux 2.6.31.
</p>
<table summary="LOC">
  <tr><th>LOC</th><th># templates</th></tr>
  <tr><td align=right>  1-    18</td><td>######################################## (685)</tr>
  <tr><td align=right> 19-    36</td><td>############ (210)</tr>
  <tr><td align=right> 37-    55</td><td>#### (78)</tr>
  <tr><td align=right> 56-    73</td><td># (33)</tr>
  <tr><td align=right> 74-    91</td><td> (10)</tr>
  <tr><td align=right> 92-   110</td><td> (7)</tr>
  <tr><td align=right>111-   128</td><td> (4)</tr>
  <tr><td align=right>129-   147</td><td> (3)</tr>
  <tr><td align=right>148-   220</td><td> (1) x 4</tr>
  <tr><td align=right>221-   294</td><td> (0) x 4</tr>
  <tr><td align=right>295-   312</td><td> (1)</tr>
</table>

<p>
Most of the sanitization functions chosen were plain text&rarr;HTML,
so the non-contextual auto-sanitization.
</p>
<table summary="distribution of escaping directives">
  <tr><td><code>|escapeHtml</code><td>602<td>
      <td><code>|escapeUri</code><td>15<td></tr>
  <tr><td><code>|escapeHtmlAttribute</code><td>380<td>
      <td><code>|escapeHtmlRcdata</code><td>10<td></tr>
  <tr><td><code>|filterNormalizeUri, |escapeHtmlAttribute</code><td>231<td>
      <td><code>|escapeHtmlAttributeNospace</code><td>7<td></tr>
  <tr><td><code>|escapeJsValue</code><td>39<td>
      <td><code>|filterHtmlIdent</code><td>3<td></tr>
  <tr><td><code>|filterCssValue</code><td>33<td>
      <td><code>|filterNormalizeUri</code><td>1<td></tr>
  <tr><td><code>|escapeJsString</code><td>27<td></tr>
</table>

<p>
268 out of 1348 interpolation sites require runtime filtering (19.9)%,
mostly <code>filterNormalizeUri</code>.
</p>

<p>
The benchmark runs over a large template with dummy data that is meant to be representative of the application
using it.  The benchmarks range from 15.2-16.8 ms and the standard-deviation is roughly 0.6 ms, which puts the
runtime-cost of the sanitization functions in the noise.
</p>
<pre>
No sanitization                   : 50% Scenario 16709334.99 ns; &sigma;= 615548.54 ns @ 10 trials
Non-contextual auto-sanitization  : 50% Scenario 16835324.39 ns; &sigma;=6030836.03 ns @ 10 trials
Full contextual auto-sanitization : 50% Scenario 15227861.39 ns; &sigma;= 616193.00 ns @ 10 trials
</pre>

<p>
In JavaScript, a state-machine based runtime contextual
auto-sanitization approach shows a 3-4 time slowdown over string
concatenation.
</p>
<table cellspacing=4 cols=6 summary="open(Template()) benchmark">
<tbody>
<tr>
  <th># rows</th>
  <th>string +=</th>
  <th>Array.join</th>
  <th>open(Template(&hellip;))</th>
  <th>DOM</th>
  <th>render time</th>
</tr>
<tr>
  <td>1000</td>
  <td>54 ms</td>
  <td>68 ms</td>
  <td>204 ms</td>
  <td>508 ms</td>
  <td>586 ms</td>
</tr>
<tr>
  <td>5000</td>
  <td>267 ms</td>
  <td>332 ms</td>
  <td>1159 ms</td>
  <td>2528 ms</td>
  <td>1458 ms</td>
</tr></tbody></table>

<p>
We ran the same benchmark against a runtime contextual auto-sanitizer
we wrote for javascript.
The "noEscape" case simply appends all the strings to a buffer.  It
does no context inference.
The "parseOnly" case appends to a buffer and does context inference, but does
no escaping.
The "dynEscape" does context propagation and chooses one of three
escaping methods by looking at the context from the parser.
The cost of applying the escaping directive is about the same as
a string copy, and the cost of parsing and propagating context at
runtime is about 6 times that cost.
This benchmark is a good comparison for templates where the logic that
computes values to fill data holes is simple so the cost of executing
the template should approach string concatenation.
</p>

<table cellpadding=2 cellspacing=0>
  <tr align=center><td>For 1000 runs<th colspan=3>noEscape<th colspan=3>parseOnly<th colspan=2>dynEscape</th></tr>
  <tr align=right>
  <td>&nbsp;</td>
  <td>491316000 ns</td><td>(1.0)</td><td>&nbsp;</td>
  <td>2979672000 ns</td><td>(6.1)</td><td>&nbsp;</td>
  <td>3531971000 ns</td><td>(7.2)</td></tr>
</table>

<script>
if (shortVersion) {
  document.write('<style>.fullversiononly { display: none }<\/style>');
} else {
  document.write('<style>.shortversiononly { display: none }<\/style>');
}
if (!printableVersion) {
  document.write('<style>.printable { display: none }<\/style>');
} else {
  document.write('<style>a.ref:link, a.ref:visited { color: inherit; text-decoration: inherit }</style>');
}
</script>

<h3 class="printable">References</h3>
<p id="references" class="printable"></p>
<script type="text/javascript">registerOnLoad(function () {
  function span(classes, content) {
    var span = document.createElement('SPAN');
    span.className = classes;
    span.appendChild(content);
    return span;
  }

  // From quirksmode
  function getStyle(el, styleProp) {
    if (el.currentStyle) { return el.currentStyle[styleProp]; }
    if (window.getComputedStyle) {
      return document.defaultView.getComputedStyle(el, null)
        .getPropertyValue(styleProp);
    }
  }

  function isDisplayed(el) {
    while (el) {
      if (el.nodeType === 1 && getStyle(el, 'display') === 'none') {
        return false;
      }
      el = el.parentNode;
    }
    return true;
  }

  var references = document.getElementById('references');
  var links = document.getElementsByTagName('A');
  links = Array.prototype.slice.call(links);
  // Pull into an array since
  var counter = 0;
  var isLocalRe = new RegExp(
      '^' + (location.origin + location.pathname).replace(/[^a-z0-9]/ig, '\\$&') + '(?:[?#]|$)');
  for (var i = 0, n = links.length; i !== n; ++i) {
    var link = links[i];
    if (!isDisplayed(link)) { continue; }
    var url = link.href;
    if (!url || isLocalRe.test(url)) { continue; }
    var description = link.title || link.innerText || link.textContent;
    if (counter) {
      references.appendChild(document.createElement('BR'));
    }
    ++counter;
    references.appendChild(document.createTextNode(
        '[' + counter + '] : ' + description + ' @ ' + link.href));
    var parent = link.parentNode;
    var follower = link.nextSibling;
    parent.insertBefore(
        span('printable', document.createTextNode(' [' + counter + ']')), follower);
    link.className += ' ref';
  }
})</script>

<div class="fullversiononly">
<hr>
<!-- hhmts start -->Last modified: Mon Feb 13 13:26:44 EST 2012 <!-- hhmts end -->
</div>

</body> </html>
